#include <iostream>
#include <string>
using namespace std;

typedef struct Node
{
    string digit;
    struct Node *top;
    struct Node *rear;
} Node, *NodeList, *Stack, *Queue;

string map2[127] = {""};
string map1[127] = {""};

void Init(NodeList L)
{
    L->rear = L;
    L->top = L;
}

string Remove(Node *p)
{
    p->top->rear = p->rear;
    p->rear->top = p->top;
    string character = p->digit;
    free(p);
    return character;
}

void Append(NodeList &L, string newCharacter)
{
    //NodeList p = (NodeList)malloc(sizeof(Node));
    Node* p = new Node();
    p->digit = newCharacter;
    p->top = L->top;
    p->rear = L;
    L->top->rear = p;
    L->top = p;
}

string Pop(NodeList &L)
{
    return Remove(L->top);
}

void Push(Stack &S, string newCharacter)
{
    Append(S, newCharacter);
}

void InQueue(Queue &Q, string newCharacter)
{
    Append(Q, newCharacter);
}

string OutQueue(Queue &Q)
{
    return Remove(Q->rear);
}

int Empty(Stack &Q)
{
    if (Q->rear == Q->top)
    {
        return 1;
    }
    return 0;
}

void DefaultInitMap2()
{
    map2['t'] = "天";
    map2['d'] = "地";
    map2['s'] = "上";
    map2['a'] = "一只";
    map2['e'] = "鹅";
    map2['z'] = "追";
    map2['g'] = "赶";
    map2['x'] = "下";
    map2['n'] = "蛋";
    map2['h'] = "恨";
}

void DefaultInitMap1()
{
    map1['B'] = "tAdA";
    map1['A'] = "sae";
}

string LookUpmap1(char key)
{
    if (map1[key] == "")
    {
        return "" + key;
    }
    else
    {
        return map1[key];
    }
}

string Rule1(string a)
{
    string newString = "";
    bool modified = false;
    for (int i = 0; i < a.length(); i++)
    {
        newString += LookUpmap1(a[i]);
    }
    return newString;
}

void Explain(Stack &Q, Stack &S)
{
    while (!Empty(S))
    {
        string p = Pop(S);
        if (p != ")")
        {
            Push(S, Rule1(p));
        }
        else
        {
            Queue tmp = new Node();
            Init(tmp);
            while (p != "(")
            {
                p = Pop(S);
                InQueue(tmp, p);
            }
            p = Pop(tmp);
            while (!Empty(tmp))
            {
                Push(S, p);
                Push(S, Pop(tmp));
            }
            Push(S, p);
        }
    }
}

void SpeakLikeAHuman(Queue Q)
{
    while (!Empty(Q))
    {
        string tmp = OutQueue(Q);
        for (int i = 0; i < tmp.length(); i++)
        {
            cout << map2[tmp[i]];
        }
    }
    cout << endl;
}

int main()
{
    Stack *S = new Stack();
    Stack *Q = new Stack();
    Init(S);
    Init(Q);
    DefaultInitMap1();
    DefaultInitMap2();
    string s1;
    cout << "Enter Satan's Quote" << endl;
    cin >> s1;
    for(int i=0; i<s1.length(); i++){
        Push(S, s1.substr(i,1));
    }
    Explain(Q, S);
    SpeakLikeAHuman(Q);
}